/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

function TreeNode(val) {
  this.val = val
  this.left = this.right = null
}

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
export var serialize = function (root) {
  if (!root) return '[]'
  const list = [root.val]
  const queue = [root]

  while (queue.length) {
    const queueSize = queue.length
    for (let i = 0; i < queueSize; i++) {
      const node = queue.shift()
      list.push(node.left ? node.left.val : 'null')
      list.push(node.right ? node.right.val : 'null')
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }
  while (list[list.length - 1] === 'null') {
    list.pop()
  }

  return '[' + list.join(',') + ']'
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
export var deserialize = function (data) {
  try {
    data = JSON.parse(data)
  } catch {
    return null
  }
  if (data.length === 0) return null
  const head = new TreeNode(data[0])
  let queue = [head]
  let curIdx = 1
  while (curIdx < data.length) {
    const queueSize = queue.length
    for (let i = 0; i < queueSize; i++) {
      const node = queue.shift()
      if (data[curIdx] !== null && data[curIdx] !== undefined) {
        node.left = new TreeNode(data[curIdx])
        queue.push(node.left)
      }
      curIdx++

      if (data[curIdx] !== null && data[curIdx] !== undefined) {
        node.right = new TreeNode(data[curIdx])
        queue.push(node.right)
      }
      curIdx++
    }
  }
  return head
}

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
